import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;

public class Test {
    //长度最小的子数组
    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length,sum = 0,len = Integer.MAX_VALUE;
        for(int left = 0,right = 0;right < n;right++){
            sum += nums[right];//进窗口
            while(sum >= target){//判断
                len = Math.min(len,right - left + 1);//更新结果
                sum -= nums[left++];//出窗口
            }
        }
        return len == Integer.MAX_VALUE ? 0 : len;
    }

    public static void main1(String[] args) {
        String str = "abcabc";
        int ret = lengthOfLongestSubstring(str);
        System.out.println(ret);
    }

    //无重复字符的最长字串
    public static int lengthOfLongestSubstring(String str) {
        char[] s = str.toCharArray();
        // char[] hash = new char[128];//用字符数组模拟哈希表
        HashMap<Character,Integer> hash = new HashMap<>();
        int len = 0,n = str.length();//利用hashMao 解决
        for(int left = 0,right = 0;right < n;right++){
            hash.put(s[right],hash.getOrDefault(s[right],0) + 1);//进窗口
            while(hash.get(s[right]) > 1){//判断
                hash.put(s[left],hash.get(s[left]) - 1);
                left++;//出窗口
            }
            len = Math.max(right - left + 1,len);
        }
        return len;
    }

    //最大连续一的个数
    public int longestOnes(int[] nums, int k) {
        int zero = 0,n = nums.length,len = 0;
        for(int left = 0,right = 0;right < n;right++){
            if(nums[right] == 0) zero++;//进窗口
            while(zero > k){ //判断
                if(nums[left] == 0) zero--;//出窗口
                left++;
            }
            len = Math.max(len,right - left + 1);//更新结果
        }
        return len;
    }

    public static void main2(String[] args) {
        int[] nums = {8828,9581,49,9818,9974,9869,9991,10000,10000,10000,9999,9993,9904,8819,1231,6309};
        int ret = minOperations(nums,134365);
        System.out.println(ret);
    }

    //将x减到0的最⼩操作数
    //正难则反
    public static int minOperations(int[] nums, int x) {
        int total = 0,n = nums.length;
        for(int i = 0;i < n;i++) total += nums[i];//求和
        int target = total - x,sum = 0,len = -1;
        if(target < 0) return -1;//处理细节
        for(int left = 0,right = 0;right < n;right++){
            sum += nums[right];//进窗口
            while(sum > target) sum -= nums[left++];//判断和出窗口
            if(sum == target) len = Math.max(len,right - left + 1);//更新结果
        }
        //应让len = -1 否则会出现解答错误
        return len == -1 ? len : n - len;
    }

    //水果成篮
    //使用哈希表方式实现
    public int totalFruit1(int[] fruits) {
        HashMap<Integer,Integer> hash = new HashMap<>();
        int n = fruits.length,len = 0;
        for(int left = 0,right = 0;right < n;right++){
            //进窗口
            int in = fruits[right];
            hash.put(in,hash.getOrDefault(in,0) + 1);
            while(hash.size() > 2){//判断
                int out = fruits[left++];//出窗口
                hash.put(out,hash.get(out) - 1);
                if(hash.get(out) == 0) hash.remove(out);
            }
            len = Math.max(len,right - left + 1);//更新结果
        }
        return len;
    }

    public static void main3(String[] args) {
        int[] fruits = {1,2,3,2,2};
        int ret = totalFruit(fruits);
        System.out.println(ret);
    }
    //使用数组模拟哈希表实现
    public static int totalFruit(int[] fruits) {
        int n = fruits.length,len = 0,kinds = 0;
        int[] hash = new int[n + 1];
        for(int left = 0,right = 0;right < n;right++){
            int in = fruits[right];
            if(hash[in] == 0) kinds++;
            hash[in]++;
            while(kinds > 2){
                //out 应该是fruits里的 left
                int out = fruits[left++];
                hash[out]--;
                if(hash[out] == 0) kinds--;
            }
            len = Math.max(len,right - left + 1);
        }
        return len;
    }

    public static void main4(String[] args) {
        String s = "ccbaebabacd";
        String p = "abc";
        List<Integer> ret = findAnagrams(s,p);
        System.out.println(ret.toString());
    }

    //找到字符串中所有字⺟异位词
    public static List<Integer> findAnagrams(String s, String p) {
        int m = p.length(),n = s.length();
        char[] pChar = p.toCharArray();
        char[] sChar = s.toCharArray();
        int count = 0;//统计有效字符的个数
        List<Integer> ret = new ArrayList<>();
        int[] hashP = new int[26];
        int[] hashS = new int[26];
        for(int i = 0;i < m;i++) hashP[pChar[i] - 'a']++;
        for(int left = 0, right = 0;right < n;right++){
            char in = sChar[right];
            hashS[in - 'a']++;
            if(hashS[in - 'a'] <= hashP[in - 'a']) count++;
            if(right - left + 1 > m){
                char out = sChar[left];
                if(hashS[out - 'a'] <= hashP[out - 'a']) count--;
                //只有S中的有效字符 <= P中有效字符的个数 count才需要减小
                hashS[out - 'a']--;
                left++;
            }
            if(count == m) ret.add(left);
        }
        return ret;
    }

    //串联所有单词的⼦串
    public List<Integer> findSubstring(String s, String[] w) {
        List<Integer> ret = new ArrayList<>();
        int len = w[0].length(),n = s.length(),m = w.length;
        HashMap<String,Integer> hashW = new HashMap<>();
        for(String str : w){
            hashW.put(str,hashW.getOrDefault(str,0) + 1);
        }
        for(int i = 0;i < len;i++){
            // i 和 left 要分开
            int left = i;
            int right = i;
            HashMap<String,Integer> hashS = new HashMap<>();//统计窗口内所有字符出现的频率
            int count = 0;
            while(right <= n - len){
                String in = s.substring(right,right + len);
                hashS.put(in,hashS.getOrDefault(in,0) + 1);
                if(hashS.get(in) <= hashW.getOrDefault(in,0)) count++;//用get方法可能会返回NULL 无法用基本运算符表示
                if(right - left + 1 > m * len){
                    // 单词的数量 * 单词的长度
                    String out = s.substring(left,left + len);
                    if(hashS.get(out) <= hashW.getOrDefault(out,0)) count--;
                    hashS.put(out,hashS.get(out) - 1);
                    left += len;
                }
                if(count == m) ret.add(left);
                right += len;
            }
        }
        return ret;
    }

    public static void main(String[] args) {
        String s = "ADOBECODEBANC";
        String t = "ABC";
        String ret = minWindow(s,t);
        System.out.println(ret);
    }
    //最小覆盖子串

    public static String minWindow(String ss, String tt) {
        char[] t = tt.toCharArray();
        char[] s = ss.toCharArray();

        int[] hashT = new int[128];//统计t中字符出现的频次
        int kinds = 0;//统计t中字符的种类
        for(char ch : t)
            if(hashT[ch]++ == 0) kinds++;
        int[] hashS = new int[128];
        int count = 0;//统计窗口中有效字符的种类
        int minLen = Integer.MAX_VALUE,begin = -1;
        for(int left = 0,right = 0;right < s.length;right++){
            char in = s[right];
            if(++hashS[in] == hashT[in]) count++;
            while(count == kinds){ // 判断
                int len = right - left + 1;
                if(len < minLen){
                    minLen = len;
                    begin = left;
                }
                char out = s[left++];// 出窗口 + 维护
                if(hashS[out]-- == hashT[out]) count--;// hash[out]-- 表示将窗口中该字符出现的次数减一
            }
        }

        if(begin == -1) return new String();
        else return ss.substring(begin,begin + minLen);
    }



}
